https://leetcode.cn/problems/implement-stack-using-queues/description/



typedef int QDatatype;
typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	tmp->next = NULL;
	tmp->val = x;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = tmp;
	}
	else
	{
		pq->ptail->next = tmp;
		pq->ptail = tmp;
	}
	pq->size++;

}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* tmp = pq->phead;
		pq->phead = pq->phead->next;
		free(tmp);

	}
	pq->size--;

}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->size);
	return pq->phead->val;
}
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->size);
	return pq->ptail->val;
}

typedef struct {
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&ps->q1);
	QueueInit(&(ps->q2));
	return ps;
}

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* empty = &obj->q1;
	Queue* nonEmpty = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		nonEmpty = &obj->q1;
		empty = &obj->q2;
	}

	while (QueueSize(nonEmpty) > 1)
	{
		QDatatype front = QueueFront(nonEmpty);
		QueuePush(empty, front);
		QueuePop(nonEmpty);
	}
	QDatatype ret = QueueFront(nonEmpty);
	QueuePop(nonEmpty);
	return ret;


}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);

	}
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}